package cn.zifangsky.queue.questions;

import org.junit.Test;

import cn.zifangsky.queue.LinkQueue;
import cn.zifangsky.queue.Queue;
import cn.zifangsky.stack.Stack;

/**
 * 如何使用两个队列来实现一个栈？
 * 
 * @author zifangsky
 *
 */
class StackWithTwoQueues<K extends Object> implements Stack<K> {
	private Queue<K> queue1;
	private Queue<K> queue2;

	public StackWithTwoQueues() {
		queue1 = new LinkQueue<>();
		queue2 = new LinkQueue<>();
	}

	@Override
	public boolean isEmpty() {
		
		return queue1.isEmpty() && queue2.isEmpty();
	}

	@Override
	public boolean isFull() {
		return false;
	}

	/**
	 * 入栈：对不为空的队列执行入队操作
	 * @时间复杂度 O(1)
	 * @param data
	 */
	@Override
	public void push(K data) {
		if(!queue1.isEmpty()){
			queue1.push(data);
		}else{
			queue2.push(data);
		}
	}

	/**
	 * 出栈：如果当前队列不为空，则将n-1个元素移到另一个队列，删除当前队列中的最后一个元素
	 * @时间复杂度 O(n)
	 * @return
	 */
	@Override
	public K pop() {
		if(!queue1.isEmpty()){ //queue1不为空
			int size = queue1.size();
			for(int i=0;i<size-1;i++){
				queue2.push(queue1.pop());
			}
			
			return queue1.pop();
		}else if(!queue2.isEmpty()){ //queue2不为空
			int size = queue2.size();
			for(int i=0;i<size-1;i++){
				queue1.push(queue2.pop());
			}
			
			return queue2.pop();
		}else{
			throw new RuntimeException("Stack Empty!");
		}
	}

	/**
	 * 类似上面出栈操作
	 * @return
	 */
	@Override
	public K top() {
		if(!queue1.isEmpty()){ //queue1不为空
			int size = queue1.size();
			for(int i=0;i<size-1;i++){
				queue2.push(queue1.pop());
			}
			
			K result = queue1.pop();
			queue2.push(result);
			
			return result;
		}else if(!queue2.isEmpty()){ //queue2不为空
			int size = queue2.size();
			for(int i=0;i<size-1;i++){
				queue1.push(queue2.pop());
			}
			
			K result = queue2.pop();
			queue1.push(result);
			
			return result;
		}else{
			throw new RuntimeException("Stack Empty!");
		}
	}

	@Override
	public int size() {
		return queue1.size() + queue2.size();
	}

	@Override
	public void print() {
		if(!queue1.isEmpty()){
			queue1.print(data -> System.out.print(data + " "));
		}else if(!queue2.isEmpty()){
			queue2.print(data -> System.out.print(data + " "));
		}
	}

	@Override
	public void deleteStack() {
		queue1 = new LinkQueue<>();
		queue2 = new LinkQueue<>();
	}

}

public class Problem_003_TwoQueuesImplementStack {

	@Test
	public void testMethods() {
		Stack<Integer> stack = new StackWithTwoQueues<>();
		stack.push(1);
		stack.push(2);
		stack.push(3);
		stack.push(4);

		stack.print();
		System.out.println();

		stack.pop();
		stack.pop();
		System.out.println("此时栈顶元素： " + stack.top());
		
		stack.push(5);
		stack.push(6);
		stack.pop();
		
		stack.print();
	}
}
